//https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?tpId=13&tqId=23271&ru=%2Fpractice%2F0e26e5551f2b489b9f58bc83aa4b6c68&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13
//思想：solution1:快速排序！！！单纯的partion是解决不了这个问题的；
//思想：使用消除方法，原理：出现不同值，就--；相同值++

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

class Solution1 {
  public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if (numbers.empty()) return 0;
        if (numbers.size() ==  1) return numbers[0];
        //快速排序
        quickSort(numbers, 0, numbers.size() - 1);
        int mid = (numbers.size() - 1) / 2;

        int mid_val = numbers[mid];
        int nus = 0;
        for (int i = 0; i < numbers.size(); ++i) {
            if (numbers[i] == mid_val) {
                nus = nus + 1;
            }
        }
        if (nus <= (numbers.size() / 2)) {
            return 0;

        }

        return mid_val;
    }


    void quickSort(vector<int>& numbers, int l, int r) {
        if (l < r) {

            int* p = partition(numbers, l, r);
            quickSort(numbers, l, p[0] - 1);
            quickSort(numbers, p[0] + 1, r);
            delete[] p;
        }

    }
    int* partition(vector<int>& numbers, int l, int r) {

        int less = l - 1;
        int more = r;
        while (l < more) {
            if (numbers[l] < numbers[r]) {
                std::swap(numbers[++less], numbers[l++]);
            } else if (numbers[l] > numbers[r]) {
                std::swap(numbers[l], numbers[--more]);
            } else {
                ++l;
            }
        }
        std::swap(numbers[more], numbers[r]);
        return new int[] {++less, more};
    };
};

class Solution2 {
  public:
    int MoreThanHalfNum_Solution(vector<int> nums) {
        int res_val = 0, res_num = 0;
        if (nums.empty()) return res_val;
        for (int i = 0; i < nums.size(); ++i) {
            if (res_num == 0) {
                res_num = 1;
                res_val = nums[i];
            } else {
                if (nums[i] == res_val) {
                    ++res_num;
                } else {
                    --res_num;
                }

            }
        }
        return res_val;
    }
};